#include <stdio.h>
#include <stdlib.h>
//第一关代码

struct node
{//此处填写代码，定义链表结点类型，包含一个存放整型数据的 data 成员，和一个指向下一个结点的next成员
    int data;
    struct node * next;
};

struct node *mycreateList()
{//此处填写代码，创建一个只有一个头结点的空链表，头节点的数据域赋值为0，并将表头结点的地址返回
  struct node * head = (struct node *)malloc(sizeof(struct node));
  if (NULL == head) 
      return NULL;
  head->data = 0;
  head->next = NULL;
  return head;
}


//第二关代码

void myinsertHead(struct node * head, int insData )
{
	/*在此处完成任务，实现在head为表头d 链表的头插数据元素insData的功能*/
	//begin
    struct node * p = (struct node *)malloc(sizeof(struct node));
    if (NULL == p) {
        printf ("Out of Space!\n");
        return;
    }
    p->data = insData;
    p->next = head->next;
    head->next = p;
	//end 
}

void myinsertTail(struct node *  head , int insData )
{
	/*在此处完成任务，在head为表头的单链表表尾插入数据元素insData*/
	//begin
    struct node * p = (struct node *)malloc(sizeof(struct node));
    if (NULL == p) {
        printf ("Out of Space!\n");
        return;
    }
    p->data = insData;
    p->next = NULL;
    // locate to tail
    struct node * tail = NULL;
    for (tail = head; NULL != tail->next; tail = tail->next);
	tail->next = p;
	//end 	
}

void myprintList(struct node *L)
{
     /*在此处完成任务，输出head为表头链表中的数据，每输出一个数据换一行*/
	//begin
    for (struct node * p = L->next; NULL != p; p = p->next)
        printf("%d\n", p->data);
	//end 
    
}

//第三关代码
 void reverseList_link( struct node *L)
 {
    // 16班陈锦程的代码, 也很不错, 比我少了一个变量
//    struct node *p,*t;
//    p=L->next;
//    while(p->next) {
//        t = p->next;
//        p->next = t->next;
//        t->next = L->next;
//        L->next = t;
//    }

// 下面是我的代码
    //请在此处填入代码，实现链表逆置功能 
 	//begin
 	
    /* 置换示意图 
     * head->[1]->(2)->3->...
     * head->(2)->[1]->3->...
     * 第一个周期完成
     * head->[2->1]->(3)->...
     * head->(3)->[2->1]->...
     * 第二个周期完成
     * head->[3->2->1]->...
     * ...
     */
    struct node * start = NULL, * end = NULL, * p = NULL;
    start = end = L->next;
 	while (NULL != end->next) {
        // 将p指向将要置换的元素——整体后一元素
        p = end->next;
        // 将整体与p置换, p成为头节点后的第一个节点
        L->next = p;
        // 将原p后的元素连接到整体上, 等待下一次置换
        end->next = p->next;
        // 将整体链接到p上
        p->next = start;
        // 将p融入整体
        start = p;
     }
 	 
	//end 
 }


//第四关代码
int locateAndChange( struct node *L, int data)
 {
    //请在此处填入代码，在头结点为L的链表中查找 与data值相等的第一个结点，若能找到该结点，则将该结点的值与前驱结点的值交换
    //若未找到与data值相等的结点，则返回值为-1，若找到的结点无前驱结点，则返回值为0，否则返回值为前驱结点的值
 	//begin
    if(data == L->next->data)
        return 0;
    for(struct node * p = L->next; NULL != p->next; p = p->next)
        if(data == p->next->data) { 
            p->next->data = p->data;
            p->data = data;
            return p->next->data;
        }
    return -1;
 
	//end 
 }

//第五关代码
int destroyList(struct node *L)
{
  //请在此处填写代码，实现将链表L的结点空间回收
 //返回值为回收结点的个数，含头结点在内

    struct node * pre = NULL;
    struct node * post = NULL;
    int count = 0;
    for (pre = post = L; pre != NULL; pre = post) {
        post = pre->next;
        free(pre);
        pre = NULL;
        count++;
    }
    return count;
}


